In order to reduce the delay time of disaster relief materials distribution and the total transportation time of disaster relief vehicles, the concept of urgency was introduced to establish a vehicle routing problem model of disaster relief vehicles based on urgency, and an improved Genetic Algorithm (GA) was designed to solve the model. Firstly, multiple strategies were used to generate the initial population. Then, an urgency-based task redistribution algorithm was proposed as local search operator. The proposed algorithm achieved the optimal delay time and total transportation time based on urgency. The delay time was reduced by rescheduling the vehicle or adjusting the delivery sequence for delay placements. The routes of the vehicles without delay were optimized to reduce the total transportation time. In the experiments, the proposed algorithm was compared with First-Come-First-Served (FCFS) algorithm, Sort by URGency (URGS) and GA on 17 datasets. Results show that the Genetic Algorithm with Task Redistribution strategy based on Urgency Degree (TRUD-GA) reduces the average delay time by 25.0% and decreases the average transportation time by 1.9% compared with GA, and has more obvious improvement compared with FCFS and URGS algorithms.